//
// Created by 朱语 on 2022/7/26.
//

#include "tree.h"
#include <iostream>
#include <stack>
#include <queue>

/*------public------*/

tree::tree() {
    this->root = nullptr;
}

tree::~tree() {
    postDelete(&root);
}



void tree::build(vector<int> &preorder, vector<int> &inorder) {
    int size = preorder.size();
    root = buildTree(preorder,inorder,0,size-1,0,size-1);
}


void tree::preorderTraversal() {
    cout<<"preorderTraversal"<<endl;
    preorder(this->root);
    cout<<endl;
    cout<<"pre-iterator"<<endl;
    preorder_iter();
    //cout<<endl;
}

void tree::inorderTraversal() {
    cout<<"inorderTraversal"<<endl;
    inorder(this->root);
    cout<<endl;
    cout<<"in-iterator"<<endl;
    inorder_iter();
}

void tree::postorderTraversal() {
    cout<<"postorderTraversal"<<endl;
    postorder(this->root);
    cout<<endl;
    cout<<"post-iterator"<<endl;
    postorder_iter();
}

void tree::levelTraversal() {
    cout<<"levelTraversal"<<endl;
    level_iter();
}




/*-------private-------*/

TreeNode* tree::buildTree(vector<int>& preorder,vector<int> inorder,int pstart,int pend,int istart,int iend){
    if(pend < pstart || iend < istart)
        return nullptr;
    TreeNode* ptr = new TreeNode(preorder[pstart]);

    int idx = istart;//根节点在中序遍历中的位置
    for(; idx <= iend ; idx++){
        if(inorder[idx] == preorder[pstart])
            break;
    }

    int pidx = pstart+(idx - istart) + 1;//先序遍历右子树的根节点位置
    //idx - istart是左子树的节点个数
    ptr->left = buildTree(preorder,inorder,pstart+1,pidx-1,istart,idx-1);
    ptr->right = buildTree(preorder,inorder,pidx,pend,idx+1,iend);
    return ptr;
}

void tree::postDelete(TreeNode** _root){
    TreeNode* root = (*_root);
    if(root->left == nullptr && root->right == nullptr){
        //delete *_root;
        delete root;
        return;
    }
    postDelete(&(root->left));
    postDelete(&(root->right));
    //delete *_root;
    delete root;
}

void tree::preorder(TreeNode *root) {
    if(root == nullptr)
        return;
    cout<<root->val<<" ";
    if(root->left)
        preorder(root->left);
    if(root->right)
        preorder(root->right);
}

void tree::inorder(TreeNode *root) {
    if(root == nullptr)
        return;
    if(root->left)
        inorder(root->left);
    cout<<root->val<<" ";
    if(root->right)
        inorder(root->right);
}

void tree::postorder(TreeNode *root) {
    if(root == nullptr)
        return;
    if(root->left)
        postorder(root->left);
    if(root->right)
        postorder(root->right);
    cout<<root->val<<" ";
}


/*------迭代方式实现，重点------*/
void tree::preorder_iter() {
    stack<TreeNode*> s;
    s.push(root);
    while(!s.empty()){
        TreeNode* ptr = s.top();
        s.pop();
        cout<<ptr->val<<" ";
        if(ptr->right)
            s.push(ptr->right);
        if(ptr->left)
            s.push(ptr->left);
    }
}

//中序遍历，左根右
void tree::inorder_iter() {
    stack<TreeNode*> s;
    TreeNode* ptr = root;
    //左子树入栈
    while(ptr){
        s.push(ptr);
        ptr = ptr->left;
    }
    while(!s.empty()){
        ptr = s.top();
        s.pop();
        //思想类似于递归,只是把递归调用的系统栈换成了自己定义的栈
        //!!对于任意当前弹出的节点，其左子树均已遍历过!!
        //所以遍历当前节点
        cout<<ptr->val<<" ";
        //转到其右子树，当做新树处理，同样遍历其左子树
        ptr = ptr->right;
        while(ptr){
            s.push(ptr);
            ptr = ptr->left;
        }
    }
}

/*
 * while(ptr){
 *     s.push(ptr);
 *     ptr = ptr->left;
 * }
 * 这段代码重复写了两次，可以参考README中的链接博客
 * https://blog.csdn.net/weixin_46308081/article/details/113818093
 * 的写法，只需要修改while的循环条件即可减少一次重复
 * 写两次纯属个人习惯
 */

void tree::postorder_iter() {
    //很烦
    stack<TreeNode*> s;
    TreeNode* ptr = root;
    TreeNode* temp = nullptr;//用于标记右子树是否访问过
    //放入左子树
    while(ptr){
        s.push(ptr);
        ptr = ptr->left;
    }
    //开始遍历
    while(!s.empty()){
        ptr = s.top();
        //不马上弹出

        //如果存在未被访问的右子树，则访问右子树
        //节点移到右子树的根节点，然后视作新的树，重新压入新树的左子树
        if(ptr->right && ptr->right != temp){
            ptr = ptr->right;
            while(ptr){
                s.push(ptr);
                ptr = ptr->left;
            }
        }
        else{
            //否则遍历当前节点
            cout<<ptr->val<<" ";
            s.pop();
            temp = ptr;
            ptr = nullptr;
        }
    }
}

void tree::level_iter() {
    queue<TreeNode*> q, temp;
    q.push(root);
    while(!q.empty()){
        TreeNode* ptr = q.front();
        q.pop();
        if(ptr == nullptr){
            cout<<"null"<<" ";
            continue;
        }
        else
            cout<<ptr->val<<" ";

        //if(ptr->left)
             temp.push(ptr->left);
        //if(ptr->right)
            temp.push(ptr->right);
        if(q.empty()){
            cout<<",";
            while(!temp.empty()){
                q.push(temp.front());
                temp.pop();
            }
        }
    }
}